/**
 * @version: V1.0
 * @Title: Test06_IsBST.java
 * @Description:
 * @author wangshipeng
 * @date 2022-01-25 23:18
 * @Copyright: 2022-01-25
 */

package com.peng.tree.test_code.dp;

import com.peng.tree.Node;

/**
 * @author wangshipeng
 * @ClassName: Test06_IsBST
 * @Description: 判断一棵树是否是平衡二叉树
 * 平衡树的定义：树的左子树高度之差<=1  &&  左右子树皆为平衡二叉树
 * @date 2022-01-25 23:18
 */
public class Test06_IsBalanceTree {

    public static TreeInfo isBST(Node head) {
        if (head == null) {
            return new TreeInfo(0, true);
        }
        TreeInfo leftInfo = isBST(head.left);
        TreeInfo rightInfo = isBST(head.right);


        //左树是平衡树，右树也是平衡树， 并且当前节点的左右高度差<=1，此时才算是平衡的
        boolean isBST = leftInfo.isBST && rightInfo.isBST && Math.abs(leftInfo.height - rightInfo.height) <= 1;
        int height = Math.max(leftInfo.height, rightInfo.height) + 1;
        return new TreeInfo(height, isBST);
    }

    public static void main(String[] args) {
        Node node = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        Node node6 = new Node(6);
        Node node7 = new Node(7);
        Node node8 = new Node(8);
        Node node9 = new Node(9);
        Node node10 = new Node(10);

        node.left = node2;
        node.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;
        node3.right = node7;
        node4.left = node8;
        node4.right = node9;

//        node8.left = node10;
         /*
                   1
             2              3
           4    5         6     7
         8   9

         */
        System.out.println(isBST(node).isBST);
    }

    static class TreeInfo {
        int height;
        boolean isBST;

        public TreeInfo(int height, boolean isBST) {
            this.height = height;
            this.isBST = isBST;
        }
    }

}
